package algorithm.backtracing;

import util.GsonUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 无限多重背包问题
 *
 * 39. Combination Sum
 * Leetcode : https://leetcode.com/problems/combination-sum/
 * Diffculty : Medium
 *
 * 给一个整数的数组和一个 target 数字，找出其中所有唯一的组合，使得组合中的和为target
 * 1)其中元素可以复用
 * 2)所有数字为正数
 * 3)全部组合不能重复
 *
 * Example:
 * Input: candidates=[2,3,6,7], target=7
 * Output:
 * [
 *  [7],
 *  [2,2,3]
 * ]
 *
 * @Author Antony
 * @Since 2018/11/12 16:25
 */
public class CombinationSum {

    public static void main(String[] args) {
        int[] arr = new int[]{2,3,6,7};
        int target = 7;
        System.out.println(GsonUtil.toJson(combinationSum(arr, target)));
    }

    /**
     * leetcode : 10ms - 98.99%
     * @param candidates
     * @param target
     * @return
     */
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);    // 需要先排序，以去重
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }


    /**
     * 回溯法
     * @param result
     * @param tempList
     * @param nums
     * @param remain
     * @param start
     */
    private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int remain, int start){
        if(remain < 0){
            return;
        }
        if(remain == 0){
            result.add(new ArrayList<>(tempList));
        }else{
            for(int i=start; i<nums.length; i++){
                tempList.add(nums[i]);
                backtrack(result, tempList, nums, remain-nums[i], i);
                tempList.remove(tempList.size() - 1);
            }
        }
    }


}
